import sortedcontainers


class Solution(object):
    def reversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        stack = sortedcontainers.SortedList()
        n = len(nums)
        if n <= 1:
            return 0
        stack.add(nums[0])
        t = 0
        for i in range(1, n):
            index = stack.bisect(2 * nums[i])
            t += len(stack) - index
            stack.add(nums[i])
        return t


data = Solution()
nums = [2, 4, 3, 5, 1]
print(data.reversePairs(nums))
nums = [1, 3, 2, 3, 1]
print(data.reversePairs(nums))
